lib/Mi manual de algoritmos/version_world_finals_2009/src/estructuras/fenwick.cpp

   1 class FenwickTree{
   2   vector<long long> v;
   3   int maxSize;
   4
   5 public:
   6   FenwickTree(int _maxSize) : maxSize(_maxSize+1) {
   7     v = vector<long long>(maxSize, 0LL);
   8   }
   9
  10   void add(int where, long long what){
  11     for (where++; where <= maxSize; where += where & -where){
  12       v[where] += what;
  13     }
  14   }
  15
  16   long long query(int where){
  17     long long sum = v[0];
  18     for (where++; where > 0; where -= where & -where){
  19       sum += v[where];
  20     }
  21     return sum;
  22   }
  23
  24   long long query(int from, int to){
  25     return query(to) - query(from-1);
  26   }
  27
  28 };